//给定一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 
//values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。 
//
// 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj =
// ? 的结果作为答案。 
//
// 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替
//代这个答案。 
//
// 注意：输入总是有效的。可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。 
//
// 
//
// 示例 1： 
//
// 
//输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"]
//,["b","a"],["a","e"],["a","a"],["x","x"]]
//输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
//解释：
//条件：a / b = 2.0, b / c = 3.0
//问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
//结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
// 
//
// 示例 2： 
//
// 
//输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], 
//queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
//输出：[3.75000,0.40000,5.00000,0.20000]
// 
//
// 示例 3： 
//
// 
//输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],[
//"a","c"],["x","y"]]
//输出：[0.50000,2.00000,-1.00000,-1.00000]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= equations.length <= 20 
// equations[i].length == 2 
// 1 <= Ai.length, Bi.length <= 5 
// values.length == equations.length 
// 0.0 < values[i] <= 20.0 
// 1 <= queries.length <= 20 
// queries[i].length == 2 
// 1 <= Cj.length, Dj.length <= 5 
// Ai, Bi, Cj, Dj 由小写英文字母与数字组成 
// 
//
// 
//
// 
// 注意：本题与主站 399 题相同： https://leetcode-cn.com/problems/evaluate-division/ 
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 图 数组 最短路 👍 53 👎 0


package LeetCode.editor.cn;


import java.util.*;

/**
 * @author ldltd
 * @date 2025-04-15 09:23:15
 * @description LCR 111.除法求值
 
 */
 
public class VlzXQL {
    public static void main(String[] args) {
    //测试代码
    VlzXQL fun = new VlzXQL();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /*dfs，把问题转化为带权的图，先构建，然后对每次查询遍历*/
    Map<String,List<Node>> map;
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        map=new HashMap<>();
        int size=equations.size();
        //先保存边权
        for (int i = 0; i < size; i++) {
            if(!map.containsKey(equations.get(i).get(0))){
                map.put(equations.get(i).get(0),new ArrayList<>());
            }
            if(!map.containsKey(equations.get(i).get(1))){
                map.put(equations.get(i).get(1),new ArrayList<>());
            }
            map.get(equations.get(i).get(0)).add(new Node(equations.get(i).get(1),values[i]));
            map.get(equations.get(i).get(1)).add(new Node(equations.get(i).get(0),1.0/values[i]));
        }
        int cnt=0;
        double [] res=new double[queries.size()];
        for (List<String> query : queries) {
            res[cnt++]=bfs(query);
        }
        return res;
    }
    private double bfs(List<String> query){
        if(!map.containsKey(query.get(0))||!map.containsKey(query.get(1))) return -1.0;
        Set<String> set=new HashSet<>();
        Deque<Node> q=new ArrayDeque<>();
        //这里队列除了保存节点名，还需要保存乘积
        q.offer(new Node(query.get(0),1.0));
        //标记是否访问
        set.add(query.get(0));
        while (!q.isEmpty()){
            Node p=q.poll();
            if(p.id.equals(query.get(1))) return p.num;
            //访问邻接节点
            for (Node node : map.get(p.id)) {
                if(!set.contains(node.id)){
                    q.offer(new Node(node.id,node.num*p.num));
                    set.add(node.id);
                }
            }
        }
        return -1.0;
    }
    class Node{
        //领接节点代表的字符串
        String id;
        //边权
        double num;
        public Node(String i,double n){
            id=i;
            num=n;
        }
    }

    public double[] calcEquation1(List<List<String>> equations, double[] values, List<List<String>> queries) {
        map=new HashMap<>();
        int n=equations.size();
        double [] res=new double[queries.size()];
        //把节点和边权存储
        for (int i = 0; i < n; i++) {
            //被除数，除数
            String dividend = equations.get(i).get(0);
            String divisor = equations.get(i).get(1);

            if(!map.containsKey(dividend)){
                map.put(dividend,new ArrayList<>());
            }
            if(!map.containsKey(divisor)){
                map.put(divisor,new ArrayList<>());
            }
            //放入边权
            map.get(dividend).add(new Node(divisor, values[i]));
            map.get(divisor).add(new Node(dividend,1.0/values[i]));
        }

        int cnt=0;
        //遍历问题
        for (List<String> query : queries) {
            //深度，初始是1
            res[cnt]=dfs(query.get(0), query.get(1),1.0,new HashSet<>());
            cnt++;
        }
        return  res;
    }
    //当前节点，目标节点，之前的乘积结果，路径
    private  double dfs(String cur, String dest, double pre, Set<String> set){
        //如果map不包含当前节点，或者已经走过当前了，说明这条路走不通
        if(!map.containsKey(cur)||set.contains(cur)){
            return -1;
        }
        //走到了终点，返回
        if(cur.equals(dest)) return pre;
        //集合添加走过的节点
        set.add(cur);
        //遍历领接节点
        for (Node node : map.get(cur)) {
            //继续深度，倍数乘上一个节点的倍数
            double temp=dfs(node.id,dest,pre*node.num,set);
            //如果找到了答案，就返回
            if(temp!=-1.0) return temp;
        }
        //没有找到
        return -1.0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
